/*1、编写一个程序，测试选择排序、冒泡排序和线性插入排序
在相同输入情况下的排序效率（比较次数和元素移动次数）。*/

#include<stdio.h>
#include<time.h>
#include<Windows.h>
#include<stdlib.h>
#include<string.h>

int NUM_SIZE = 20;
int MAX_MUN = 99999;
int SEED = 0;

void show_selection_sort(int* a,int n){
    int i,j,cmp,mov,cur_min,cur_min_idx,tmp;
    i = j = cmp = mov = 0;
    SYSTEMTIME pt1,pt2;
    GetSystemTime(&pt1);
    for(i=0;i<n;i++){
        cur_min = a[i];
        cur_min_idx = i;
        for(j=i+1;j<n;j++)
            if(++cmp && a[j]<cur_min){cur_min = a[j];cur_min_idx=j;}
        if(cur_min_idx!=i){a[cur_min_idx]=a[i];a[i]=cur_min;++mov;}
    }
    GetSystemTime(&pt2);
    long long total = (pt2.wMilliseconds - pt1.wMilliseconds) + (pt2.wSecond - pt1.wSecond) * 1000;
    printf("----- Selection Sort -----\nElement count: %d\nTotal time: %d ms\n",n,total);
    printf("Compare: %d\nMove: %d\n",cmp,mov);
    printf("Sort result(show first 20 elements):\n");
    if(n>20)n=20;
    for(i=0;i<n;i++)printf("%d ",a[i]);putchar('\n');
}

void show_bubble_sort(int* a,int n){
    int i,j,cmp,mov,tmp;
    cmp = mov = 0;
    SYSTEMTIME pt1,pt2;
    GetSystemTime(&pt1);
    for(i=0;i<n;i++){
        for(j=0;j<n-i-1;j++){
            if( ++cmp && a[j]>a[j+1] ){ tmp=a[j];a[j]=a[j+1];a[j+1]=tmp; ++mov; }
        }
    }
    GetSystemTime(&pt2);
    long long total = (pt2.wMilliseconds - pt1.wMilliseconds) + (pt2.wSecond - pt1.wSecond) * 1000;
    printf("----- Bubble Sort -----\nElement count: %d\nTotal time: %d ms\n",n,total);
    printf("Compare: %d\nMove: %d\n",cmp,mov);
    printf("Sort result(show first 20 elements):\n");
    if(n>20)n=20;
    for(i=0;i<n;i++)printf("%d ",a[i]);putchar('\n');
}

void show_insert_sort(int* a,int n){
    int i,j,k,mov,cmp,cur;
    cmp = mov = 0;
    SYSTEMTIME pt1,pt2;
    GetSystemTime(&pt1);
    for(i=0;i<n;i++){
        cur = a[i];
        for(j=0;j<i;j++)if( ++cmp && cur<a[j] )break;
        if(j<i)for(k=i;k>j;k--){ ++mov; a[k]=a[k-1]; }
        a[j] = cur; ++mov;
    }
    GetSystemTime(&pt2);
    long long total = (pt2.wMilliseconds - pt1.wMilliseconds) + (pt2.wSecond - pt1.wSecond) * 1000;
    printf("----- Insertion Sort -----\nElement count: %d\nTotal time: %d ms\n",n,total);
    printf("Compare: %d\nMove: %d\n",cmp,mov);
    printf("Sort result(show first 20 elements):\n");
    if(n>20)n=20;
    for(i=0;i<n;i++)printf("%d ",a[i]);putchar('\n');
}

void show_shell_sort(int* a,int n){
    // Get Exact time to milliseconds using windows API
    SYSTEMTIME pt1,pt2;
    GetSystemTime(&pt1);
    int i,j,k,l,d,mov,cmp,cur;
    cmp = mov = 0;
    d = n;
    while(d>1){
        d /= 2;
        for(k=0;k<d;k++){ // d组，做d次插入排序，甚至可以直接套上面的代码
            for(i=k;i<n;i+=d){
                cur = a[i];
                for(j=k;j<i;j+=d)if( ++cmp && cur<a[j] )break;
                if(j<i)for(l=i;l>j;l-=d){ ++mov; a[l]=a[l-d]; }
                a[j] = cur; ++mov;
            }
        }
    }
    GetSystemTime(&pt2);
    long long total = (pt2.wMilliseconds - pt1.wMilliseconds) + (pt2.wSecond - pt1.wSecond) * 1000;
    printf("----- Shell Sort -----\nElement count: %d\nTotal time: %d ms\n",n,total);
    printf("Compare: %d\nMove: %d\n",cmp,mov);
    printf("Sort result(show first 20 elements):\n");
    if(n>20)n=20;
    for(i=0;i<n;i++)printf("%d ",a[i]);putchar('\n');
}

int main(int argc,char** argv){
    int i,j,k,l;
    for(i=0;i<argc;i++){
        if( ( strcmp("-s",argv[i])==0 || strcmp("--size",argv[i])==0 ) )NUM_SIZE=atoi(argv[i+1]);
        if( ( strcmp("-m",argv[i])==0 || strcmp("--max",argv[i])==0 ) )MAX_MUN=atoi(argv[i+1]);
        if( ( strcmp("-d",argv[i])==0 || strcmp("--seed",argv[i])==0 ) )SEED=atoi(argv[i+1]);
    }
    if(SEED<0)SEED = time(NULL); srand(SEED);

    int* select = malloc(sizeof(int)*NUM_SIZE);
    int* bubble  = malloc(sizeof(int)*NUM_SIZE);
    int* insert = malloc(sizeof(int)*NUM_SIZE);
    // int* shell = malloc(sizeof(int)*NUM_SIZE);

    for(i=0;i<NUM_SIZE;i++)select[i]=bubble[i]=insert[i]=rand() % MAX_MUN;

    show_selection_sort(select,NUM_SIZE);
    show_bubble_sort(bubble,NUM_SIZE);
    show_insert_sort(insert,NUM_SIZE);
    // show_shell_sort(shell,NUM_SIZE);
    
    free(select);free(bubble);free(insert);
    return 0;
}
